
package 数据结构.单向链表;
//单向链表实现

public class ListNode<T> {

    private Node head;
    private int size = 0;

    //链表本表
    public class Node{
        T data;
        Node next;

        public Node(T data){
            this.data = data;
            next = null;
        }

    }

    //如果链表没有头结点，新结点直接成为头结点；否则新结点的next直接指向当前头结点，并让新结点成为新的头结点
    public void addHeadNode(T value) {
        Node newNode = new Node(value);
        //头结点不存在，新结点成为头结点
        if (head == null) {
            head = newNode;
            size ++;
            return;
        }
        //新结点next直接指向当前头结点
        newNode.next = head;
        //新结点成为新的头结点
        head = newNode;
        size ++;
    }

    //果链表没有头结点，新结点直接成为头结点；否则需要先找到链表当前的尾结点，并将新结点插入到链表尾部。
    public void addTailNode(T value) {
        Node newNode = new Node(value);
        //头结点不存在，新结点成为头结点
        if (head == null) {
            head = newNode;
            size ++;
            return;
        }
        //找到最后一个结点
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        //新结点插入到链表尾部
        last.next = newNode;
        size ++;
    }

    public void addNodeAtIndex(T value, int index) {
        if (index < 0 || index > size) { //注意index是可以等于size()的
            throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
        }
        if (index == 0) {  //插入到头部
            addHeadNode(value);
        } else if (index == size) {  //插入到尾部
            addTailNode(value);
        } else {  //插到某个中间位置
            Node newNode = new Node(value);
            int position = 0;
            Node cur = head;  //标记当前结点
            Node pre = null;  //记录前置结点
            while (cur != null) {
                if (position == index) {
                    newNode.next = cur;
                    pre.next = newNode;
                    size++;
                    return;
                }
                pre = cur;
                cur = cur.next;
                position++;
            }
        }
    }

    public void deleteNodeAtIndex(int index) {
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
        }
        if (index == 0) { //删除头
            head = head.next;
            return;
        }
        int position = 0;  //记录当前位置
        Node cur = head;  //标记当前结点
        Node pre = null;  //记录前置结点
        while (cur != null) {
            if (position == index) {
                pre.next = cur.next;
                cur.next = null;  //断开cur与链表的连接
                return;
            }
            pre = cur;
            cur = cur.next;
            position++;
        }
    }

    public void get(){
        Node curNode = head;
        while(curNode !=null){
            System.out.print(curNode.data+" ");
            curNode = curNode.next;
        }
        System.out.println();
    }

    public int len(){
        return this.size;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode();
        listNode.addHeadNode(1);
        listNode.addHeadNode(2);
        listNode.addHeadNode(3);
        listNode.addHeadNode(4);
        listNode.addHeadNode(5);

//        listNode.addTailNode(6);

//        listNode.addNodeAtIndex(7,1);

        listNode.get();

        System.out.println(listNode.len());

//        listNode.deleteNodeAtIndex(1);

        listNode.get();
    }


}
